package com.gitee.wsl.ext.array

import kotlin.math.max
import kotlin.math.min


fun ByteArray.indexOf(other: ByteArray): Int {
    val full = this
    for (n in 0 until full.size - other.size) if (other.indices.all { full[n + it] == other[it] }) return n
    return -1
}

fun <T> Array<T>.indexOf(needle: T): Int{
    if (isEmpty()) {
        return -1
    }
    var index = -1
    forEach {
        index++
        if( it == needle ) return index
    }
    return -1
}

/**
 * Boyer–Moore string-search algorithm
 *
 * Returns the index within this string of the first occurrence of the
 * specified substring. If it is not a substring, return -1.
 *
 * There is no Galil because it only generates one match.
 *
 * @param needle The target string to search
 * @return The start index of the substring
 */
fun <T> Array<T>.indexOf(needle: Array<T>): Int {
    if (needle.isEmpty()) {
        return 0
    }
    val charTable = makeCharTable(needle)
    val offsetTable = makeOffsetTable(needle)
    var i = needle.size - 1
    var j: Int
    while (i < this.size) {
        j = needle.size - 1
        while (needle[j] == this[i]) {
            if (j == 0) return i
            i--
            j--
        }
        // i += needle.length - j; // For naive method
        i += max(offsetTable[needle.size - 1 - j], charTable[this[i]]!!)
    }
    return -1
}

/**
 * Makes the jump table based on the mismatched character information.
 * (bad-character rule)
 */
private fun <T> makeCharTable(needle: Array<T>): HashMap<T, Int> {
    val table = hashMapOf<T, Int>()
    for (i in needle) {
        table[i] = needle.size
    }
    for (i in needle.indices) {
        table[needle[i]] = needle.size - 1 - i
    }
    return table
}

/**
 * Makes the jump table based on the scan offset which mismatch occurs.
 * (good suffix rule)
 */
private fun <T> makeOffsetTable(needle: Array<T>): IntArray {
    val table = IntArray(needle.size)
    var lastPrefixPosition = needle.size
    for (i in needle.size downTo 1) {
        if (isPrefix(needle, i)) {
            lastPrefixPosition = i
        }
        table[needle.size - i] = lastPrefixPosition - i + needle.size
    }
    for (i in 0 until needle.size - 1) {
        val slen = suffixLength(needle, i)
        table[slen] = needle.size - 1 - i + slen
    }
    return table
}

/**
 * Is needle[p:end] a prefix of needle?
 */
private fun <T> isPrefix(needle: Array<T>, p: Int): Boolean {
    var i = p
    var j = 0
    while (i < needle.size) {
        if (needle[i] != needle[j]) {
            return false
        }
        i++
        j++
    }
    return true
}

/**
 * Returns the maximum length of the substring ends at p and is a suffix.
 * (good-suffix rule)
 */
private fun <T> suffixLength(needle: Array<T>, p: Int): Int {
    var len = 0
    var i = p
    var j = needle.size - 1
    while (i >= 0 && needle[i] == needle[j]) {
        len += 1
        --i
        --j
    }
    return len
}


/**
 * Executes K-th order statistic. Average O(N).
 * Swap elements in array. At the end, the K-th element will be under index [k].
 * @param k element search ordinal number. 0 < [k] <= [to] - [from]
 * @param from index from for search in array (inclusive)
 * @param to index to for search in array (exclusive)
 * @param ascending if true search in ascending order else in descending order
 * @return k-th element from array
 */
fun <T : Comparable<T>> Array<T>.findOrderStatistic(
    k: Int,
    from: Int,
    to: Int,
    ascending: Boolean,
): T {
    val actualK = k - 1
    var left = from
    var right = to - 1

    while (true) {
        val mid = if (ascending) partitionAscending(left, right) else partitionDescending(left, right)

        when {
            mid == actualK -> return get(mid)
            actualK < mid -> right = mid - 1
            else -> left = mid + 1
        }
    }
}


/**
 * Higher the range with 1 byte while keeping length the same
 * Will return same byte array if it cannot be highered
 */
fun ByteArray.nextByteInSameLength(): ByteArray {
    val newArray = this.copyOf()
    for (i in newArray.lastIndex downTo 0) {
        if (newArray[i] != 0xFF.toByte()) {
            newArray[i]++
            return newArray
        }
    }
    return this // All bytes are max bytes
}

/**
 * Lower the range with 1 byte while keeping length the same
 * Will throw IllegalStateException if byte array cannot be lowered further
 */
fun ByteArray.prevByteInSameLength(maxLengthToRead: Int? = null): ByteArray {
    val newArray = this.copyOf()
    val startIndex = maxLengthToRead?.let { newArray.size - it.coerceAtMost(newArray.size) } ?: 0
    for (i in newArray.lastIndex downTo startIndex) {
        if (newArray[i] != 0.toByte()) {
            newArray[i]--
            return newArray
        }
        newArray[i] = 0xFF.toByte()
    }
    throw IllegalStateException("Byte array already reached the minimum value")
}

/**
 * Returns the index of the last appearance of the value `target` in
 * `array`.
 *
 *
 *
 * **Analysis**
 *
 *  * Time Complexity: `O(n)`
 *  * Space Complexity: `O(1)`
 *  * Alters Parameters: `false`
 *
 *
 *
 * @param array  an array of `byte` values, possibly empty
 * @param target a primitive `byte` value
 * @return the greatest index `i` for which `array[i] == target`,
 * or `-1` if no such index exists.
 */
fun ByteArray.lastIndexOf( target: Byte, start: Int, end: Int): Int {
    for (i in end - 1 downTo start) {
        if (this[i] == target) {
            return i
        }
    }
    return -1
}

/**
 * Returns the start position of the first occurrence of the specified `target` within `array`, or `-1` if there is no such occurrence.
 *
 *
 *
 * More formally, returns the lowest index `i` such that `java.util.Arrays.copyOfRange(array, i, i + target.length)` contains exactly
 * the same elements as `target`.
 *
 *
 *
 * **Analysis**
 *
 *  * Time Complexity: `O(n*m)`
 *  * Space Complexity: `O(1)`
 *  * Alters Parameters: `false`
 *
 *
 *
 * @param array  the array to search for the sequence `target`
 * @param target the array to search for as a sub-sequence of `array`
 */
fun ByteArray.indexOf( target: ByteArray, start: Int, end: Int): Int {
    if (target.isEmpty() || start < 0) {
        return -1
    }
    outer@ for (i in start..<min(end, size - target.size + 1)) {
        for (j in target.indices) {
            if (this[i + j] != target[j]) {
                continue@outer
            }
        }
        return i
    }
    return -1
}

/**
 * [4-33] Algorithm to determine whether there exists an i index such as ai = i given array of {a1, a2, a3 ... an}
 * Sorted and distinct case:
 */

fun findMagicIndex(array: IntArray, low: Int, high: Int): Int? {
    if (high < low) {
        return null
    }
    val mid = (low + high) / 2
    val middleElement = array[mid]
    return if (middleElement == mid + 1) {
        println("Element is at index $mid with value ${array[mid]}")
        mid + 1
    } else if (middleElement > mid + 1) {
        findMagicIndex(array, low, mid - 1)
    } else {
        findMagicIndex(array, mid + 1, high)
    }
}

/**
 * [4-34]
 *  Suppose that you are given a sorted sequence of distinct integers {a1, a2, . . . , an},
 *  drawn from 1 to m where n < m. Give an O(lg n) algorithm to find an integer ≤ m
 *  that is not present in a. For full credit, find the smallest such integer.
 *
 *  Solution: Binary search into the array.
 *  Since its sorted and starts from index 1, every element at index i should have element i.
 *
 */
private fun smallestMissingNumber(array: IntArray, low: Int, high: Int): Int {
    if (low >= high) {
        // a[i] == i so missing element is the index
        return low
    }
    if (array.first() != 1) {
        return 1
    } else if (array.last() == array.size) {
        return array.lastIndex + 1 + 1
    }
    // Calibrate to find midIndex
    val midIndex = (low - 1 + high - 1) / 2
    val midItem = array[midIndex]
    // index i should have element i
    // Since elements are distinct, if condition is not met, then there is some missing element at left
    if (midItem != midIndex + 1) {
        return smallestMissingNumber(array, low, midIndex + 1 - 1)
    } else {
        // Since a[i] == i so all left elements are sequential so missing element must be at right
        return smallestMissingNumber(array, midIndex + 1 + 1, array.size)
    }
}

/**
 * Finds the index of the minimum element in the array starting from the
 * specified index.
 *
 * @param i The starting index from which to search for the minimum element.
 * @return The index of the minimum element found in the array starting from the
 * specified index.
 */
fun <T : Comparable<T>> Array<T>.findMinimumIndex(i: Int): Int {
    var min = i
    for (j in i + 1 until this.size) {
        if (this[j] < this[min]) {
            min = j
        }
    }
    return min
}


inline fun <reified T> Array<*>.firstIsInstance(): T {
    for (element in this) if (element is T) return element
    throw NoSuchElementException("No element of given type found")
}

inline fun <reified T : Any> Array<*>.firstIsInstanceOrNull(): T? {
    for (element in this) if (element is T) return element
    return null
}